#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN=10050;
const int INF=0x3f3f3f3f;
int map[MAXN][MAXN];
int lowcost[MAXN];
bool vis[MAXN];
int n,m;
//----------*********----------
//次小生成树所增加的数组
//记录最小生成树中！！ i到j的最大边权
int path[MAXN][MAXN];
//记录边是否在mst中
bool used[MAXN][MAXN];
//记录前驱位置
int pre[MAXN];
int mst;
//----------*********----------
int prim(){
	int pos=1;
	int Min=INF;
	int ans=0;
	memset(vis,false,sizeof(vis));
    //----------*********----------
	memset(used,false,sizeof(used));
	memset(path,0,sizeof(path));
    //----------*********----------
	vis[pos]=true;
	for(int i=1;i<=n;i++){
		if(i!=pos){
			lowcost[i]=map[pos][i];
		}
        //----------*********----------
		pre[i]=1;
        //----------*********----------
	}
	for(int i=1;i<n;i++){
		Min=INF;
		for(int j=1;j<=n;j++){
			if(!vis[j] && lowcost[j]<Min){
				Min=lowcost[j];
                pos=j;
			}
		}
		ans+=Min;
		vis[pos]=true;
        //----------*********----------
		//加入mst
		used[pos][pre[pos]]=used[pre[pos]][pos]=true;
        //----------*********----------
		for(int j=1;j<=n;j++){
            //----------*********----------
			if(vis[j] && j!=pos){
				//更新从j到pos的路径上的最大边权
				//即比较j到pre[pos]和lowcost[pos] （j到mst的最小边权）
                //lowcost[pos]相当于即将加上的这条边，而path[j][pre[pos]]指已存在的树中
                //j和pre[pos]之间的最大边权
                printf("%d---%d---%d---%d---%d\n",j,pos,pre[pos],path[j][pre[pos]],lowcost[pos]);
				path[j][pos]=path[pos][j]=max(path[j][pre[pos]],lowcost[pos]);
			}
            //----------*********----------
			if(!vis[j] && lowcost[j]>map[pos][j]){
				lowcost[j]=map[pos][j];
                //----------*********----------
				//记录前驱
				pre[j]=pos;
                //----------*********----------
			}
		}
	}
    //----------*********----------
	mst=ans;
    //----------*********----------
	return ans;
}
//----------*********----------
int second_tree(){
	int ans=INF;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
            //这里一定要在没用过的边找，在用过的边找没有意义
			if(i!=j && !used[i][j]){
				//删除mst上权值最大边并加入这条路的其他边
                //比如删去i和j之间的路径的最大边权后，而i和j之间又没有直接相连，也就是map[i][j]=INF
                //肯定比ans大，ans不更新，这里为什么要用min，是因为要求的是次小，也就是要从INF往小更新
                //举个例子比如现在1--(3)--2--(4)--3  所以path[1][3]=4
                //而此时1 3有边直接相连 1--(9)--3 map[1][3]=9  ans-path[i][j]+map[i][j]这里就表示
                //断开1与3的关系，改为直接相连的边，这样仍然是生成树
				ans=min(ans,mst-path[i][j]+map[i][j]);
			}
		}
	}
	return ans;
}
//----------*********----------
int main(void){
    n=7;
    memset(map,INF,sizeof(map));
    map[1][2]=map[2][1]=7;
    map[1][4]=map[4][1]=5;
    map[2][4]=map[4][2]=9;
    map[4][5]=map[5][4]=15;
    map[4][6]=map[6][4]=6;
    map[5][6]=map[6][5]=8;
    map[6][7]=map[7][6]=11;
    map[5][7]=map[7][5]=9;
    map[2][5]=map[5][2]=7;
    map[2][3]=map[3][2]=8;
    map[3][5]=map[5][3]=5;
    int ans=prim();
    printf("%d\n",ans);
    for(int i=1;i<n;i++){
        for(int j=i+1;j<=n;j++){
            if(used[i][j]){
                printf("%d %d %d\n",i,j,map[i][j]);
            }
        }
    }
    printf("----------\n");
    for(int i=1;i<n;i++){
        for(int j=i+1;j<=n;j++){
            printf("%d %d %d\n",i,j,path[i][j]);
        }
    }
    //----------*********----------
	ans=second_tree();
	printf("%d\n",ans);
    //----------*********----------

    for(int i=1;i<=n;i++){
        printf("%d %d\n",i,pre[i]);
    }
	return 0;
}
